1272E - Nearest Opposite Parity - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;

int T,n,m;
int a[N];
int dist[N];
queue<int> q;
vector<int> sons[N];

void solve()
{
    memset(dist,0x3f,sizeof(dist));

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        int t=i-a[i];
        if(t>=1)
        {
            if(a[i]%2==a[t]%2) sons[t].push_back(i);
            else dist[i]=1;
        }

        t=i+a[i];
        if(t<=n)
        {
            if(a[t]%2==a[i]%2) sons[t].push_back(i);
            else dist[i]=1;
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(dist[i]==1) q.push(i);
    }

    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(int i=0;i<sons[u].size();i++)
        {
            int k=sons[u][i];
            if(dist[k]>dist[u]+1)
            {
                dist[k]=dist[u]+1;
                q.push(k);
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(dist[i]!=0x3f3f3f3f) cout<<dist[i]<<' ';
        else cout<<"-1 ";
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    //cin>>T;
    T=1;
    
    while(T--) 
        solve();
    
    return 0;
}